#include "Map.h"
#include <stack>
#include <float.h>


Map::Map()
: m_pMapInfo(NULL)
, m_szX(0)
, m_szY(0)
{}

Map::~Map(void)
{
	if (m_pMapInfo)
	{
		for (ULONG y = 0; y < m_szY; y++)
			free(m_pMapInfo[y]);
		free(m_pMapInfo);
	}
#ifdef _CRTDBG_MAP_ALLOC
	_CrtDumpMemoryLeaks();
#endif
}



template<class _T>
class _buf
{
private:
	_T* m_pBuf;
	size_t m_szX, m_szY;

public:
	_buf(size_t x_sz, size_t y_sz)
		: m_pBuf(NULL), m_szX(x_sz), m_szY(y_sz)
	{
		m_pBuf = (_T*)calloc(x_sz * y_sz, sizeof(_T));
	}

	_buf(size_t x_sz, size_t y_sz, _T val)
		: m_pBuf(NULL), m_szX(x_sz), m_szY(y_sz)
	{
		m_pBuf = (_T*)malloc(x_sz * y_sz * sizeof(_T));
		for(size_t i=0 ;i < (x_sz * y_sz); i++) m_pBuf[i] = val;
	}

	~_buf() { free(m_pBuf); }

	_T* operator[](size_t index) 
	{ 
		_ASSERT(index < m_szY);
		return m_pBuf + m_szX * index; 
	}

	_T& operator[](POINTU pos)
	{
		_ASSERT(pos.y < m_szY && pos.x < m_szX);
		return m_pBuf[m_szX * pos.y + pos.x];
	}
};



int Map::FindRoute(POINTU from, POINTU to, std::list<POINTU>* pRoute) const
{
	_ASSERT(from.x < m_szX && from.y < m_szY);
	_ASSERT(to.x < m_szX && to.y < m_szY);

	pRoute->clear();

	_buf<float> buf(m_szX, m_szY, FLT_MAX);
	buf[from] = 0.0f;

	std::stack<POINTU> _stk;
	_stk.push(from);

	POINT naSearchPriority[4];
	ZeroMemory(naSearchPriority, sizeof(naSearchPriority));
	LONG xdef = from.x - to.x;
	LONG ydef = from.y - to.y;
	if (abs(xdef) > abs(ydef))
	{
		naSearchPriority[0].x = xdef > 0 ? 1 : -1;
		naSearchPriority[1].y = ydef > 0 ? 1 : -1;
		naSearchPriority[2].x = naSearchPriority[0].x * -1;
		naSearchPriority[3].y = naSearchPriority[1].y * -1;
	}
	else
	{	
		naSearchPriority[0].y = ydef > 0 ? 1 : -1;
		naSearchPriority[1].x = xdef > 0 ? 1 : -1;
		naSearchPriority[2].y = naSearchPriority[0].y * -1;
		naSearchPriority[3].x = naSearchPriority[1].x * -1;
	}

	// 
	while (!_stk.empty())
	{
		POINTU p = _stk.top(); _stk.pop();
		float fVal= buf[p] + 1.0f; 
		POINTU ps[4] = { p, p, p, p };
		for (int i = 0; i < 4; i++)
			ps[i] += naSearchPriority[i];

		for (int i = 0; i < 4; i++)
		{
			if (InRange(ps[i]) && m_pMapInfo[ps[i].y][ps[i].x].bCanPass)
			{
				if (buf[ps[i]] > fVal)
				{
					buf[ps[i]] = fVal;
					_stk.push(ps[i]);
				}
			}
		}
	}

	_stk.push(to);
	for (POINTU p = to; p.x != from.x || p.y != from.y;)
	{
		POINTU ps[4] = { p, p, p, p };
		for (int i = 0; i < 4; i++)
			ps[i] += naSearchPriority[3 - i];

		float fVal = buf[p];
		int min = -1;
		for (int i = 0; i < 4; i++)
		{
			if (InRange(ps[i]))
			if (fVal > buf[ps[i]])
			{
				fVal = buf[ps[i]];
				min = i;
			}
		}
		if (min == -1) return -1;
		p = ps[min];
		_stk.push(ps[min]);
	}

	while (!_stk.empty())
	{
		pRoute->push_back(_stk.top());
		_stk.pop();
	}

	return pRoute->size();
}